package com.sise.Tree;

import com.sise.Linked.ListNode;
import java.util.LinkedList;
import java.util.Queue;

/**
 *      面试题 04.03. 特定深度节点链表
 *
 *      给定一棵二叉树，设计一个算法，创建含有某一深度上所有节点的链表（比如，若一棵树的深度为 D，则会创建出 D 个链表）。返回一个包含所有深度的链表的数组。
 *
 *      输入：[1,2,3,4,5,null,7,8]
 *
 *             1
 *           /  \
 *          2    3
 *         / \    \
 *        4   5    7
 *       /
 *      8
 *
 *      输出：[[1],[2,3],[4,5,7],[8]]
 *
 */
public class _04_03_listOfDepth {
    public ListNode[] listOfDepth(TreeNode tree) {
        int depth = getDepth(tree);                 // 获取深度
        int idx = 0;                                // 为数组递增做准备
        ListNode[] ans = new ListNode[depth];
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(tree);

        while (!queue.isEmpty()){
            int size = queue.size();
            // 设置哑结点，将头结点设置在哑结点
            ListNode pre = new ListNode(0);
            ListNode head = pre;

            for (int i = 0; i < size; i++){
                TreeNode poll = queue.poll();
                // 根据节点的值 创建对象，赋值在 head.next（下一个节点），
                // head = head.next 是因为 for 循环中的链表连接都是依靠 head 节点，如果没有这一步骤，那么后面的节点就会覆盖前面的节点。
                // [1] [1,2] 的 head 分别是 1,2
                ListNode tmp = new ListNode(poll.val);
                head.next = tmp;
                head = head.next;
                if (poll.left != null){
                    queue.offer(poll.left);
                }
                if (poll.right != null){
                    queue.offer(poll.right);
                }
            }
            // 赋值的是哑结点的下一个节点
            ans[idx++] = pre.next;
        }
        return ans;
    }

    public int getDepth(TreeNode root){
        if (root == null) return 0;
        return Math.max(getDepth(root.left), getDepth(root.right)) + 1;
    }
}
